package 剑指offer;

import java.util.Stack;

public class 镜像二叉树 {
    public static void deepdispaly(TreeNode tree) {
        if (tree != null) {
            System.out.println(tree.val);
            deepdispaly(tree.left);
            deepdispaly(tree.right);//深度遍历，线序遍历

        }
    }

    public static void Mirror(TreeNode root) {
        /*
         * 	     8
         * 	  6	10
         *  5 	7     9	     11
         *
         *
         */

        if (root == null)
            return;
        if (root.left == null && root.right == null)
            return;

        TreeNode pTemp = root.left;
        root.left = root.right;
        root.right = pTemp;

        if (root.left != null)
            Mirror(root.left);
        if (root.right != null)
            Mirror(root.right);


    }

    public static void printTree(TreeNode tree) {
        if (tree != null) {
            //System.out.print(tree.val+" ");//先序遍历
            printTree(tree.left);
            System.out.print(tree.val + " ");//MiddleMy
            printTree(tree.right);
            //System.out.print(tree.val+" ");//后序遍历
        }
    }

    static TreeNode KthNode(TreeNode pRoot, int k) {
        //通过中序遍历
        Stack<TreeNode> stack = new Stack();
        TreeNode idol = pRoot;
        int count = 0;
        while (true) {
            while (idol != null) {
                stack.push(idol);
                idol = idol.left;
            }
            if (stack.isEmpty()) {
                break;
            }
            idol = stack.pop();
            System.out.println(idol.val);
            if (++count == k) {
                return idol;
            }
            idol = idol.right;


        }
        return null;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
//        TreeNode root = new TreeNode(8);
//        root.left = new TreeNode(6);
//        root.right = new TreeNode(10);
//        root.left.left = new TreeNode(5);
//        root.left.right = new TreeNode(7);
//        root.right.left = new TreeNode(9);
//        root.right.right = new TreeNode(11);
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(3);
        root.left.left.left = new TreeNode(2);
        root.left.left.left.left = new TreeNode(1);

        TreeNode temp = root;
//        printTree(root);
//        Mirror(root);
//        System.out.println("\n");
//        printTree(root);

        printTree(KthNode(temp, 3));

    }

}
